The effects of sampling on the efficiency and accuracy of k−mer indexes: Theoretical and empirical comparisons using the human genome
Identifieur interne : 000B53 ( Main/Exploration ); précédent : 000B52; suivant : 000B54The effects of sampling on the efficiency and accuracy of k−mer indexes: Theoretical and empirical comparisons using the human genome
Auteurs : Meznah Almutairy ; Eric TorngSource :
- PLoS ONE [ 1932-6203 ] ; 2017.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
- genetics : Genome, Human.
- methods : Computational Biology, Sequence Alignment, Sequence Analysis, DNA.
- Algorithms, Databases, Genetic, Humans, Software.
Abstract
One of the most common ways to search a sequence database for sequences that are similar to a query sequence is to use a
Url:
DOI: 10.1371/journal.pone.0179046
PubMed: 28686614
PubMed Central: 5501444
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 001030
- to stream Pmc, to step Curation: 001030
- to stream Pmc, to step Checkpoint: 000695
- to stream PubMed, to step Corpus: 000C31
- to stream PubMed, to step Curation: 000C31
- to stream PubMed, to step Checkpoint: 000A93
- to stream Ncbi, to step Merge: 001B04
- to stream Ncbi, to step Curation: 001B04
- to stream Ncbi, to step Checkpoint: 001B04
- to stream Main, to step Merge: 000B56
- to stream Main, to step Curation: 000B53
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">The effects of sampling on the efficiency and accuracy of <italic>k</italic>−mer indexes: Theoretical and empirical comparisons using the human genome</title><author><name sortKey="Almutairy, Meznah" sort="Almutairy, Meznah" uniqKey="Almutairy M" first="Meznah" last="Almutairy">Meznah Almutairy</name><affiliation><nlm:aff id="aff001"></nlm:aff></affiliation></author><author><name sortKey="Torng, Eric" sort="Torng, Eric" uniqKey="Torng E" first="Eric" last="Torng">Eric Torng</name><affiliation><nlm:aff id="aff001"></nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">28686614</idno><idno type="pmc">5501444</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC5501444</idno><idno type="RBID">PMC:5501444</idno><idno type="doi">10.1371/journal.pone.0179046</idno><date when="2017">2017</date><idno type="wicri:Area/Pmc/Corpus">001030</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">001030</idno><idno type="wicri:Area/Pmc/Curation">001030</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">001030</idno><idno type="wicri:Area/Pmc/Checkpoint">000695</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000695</idno><idno type="wicri:source">PubMed</idno><idno type="RBID">pubmed:28686614</idno><idno type="wicri:Area/PubMed/Corpus">000C31</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000C31</idno><idno type="wicri:Area/PubMed/Curation">000C31</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000C31</idno><idno type="wicri:Area/PubMed/Checkpoint">000A93</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000A93</idno><idno type="wicri:Area/Ncbi/Merge">001B04</idno><idno type="wicri:Area/Ncbi/Curation">001B04</idno><idno type="wicri:Area/Ncbi/Checkpoint">001B04</idno><idno type="wicri:Area/Main/Merge">000B56</idno><idno type="wicri:Area/Main/Curation">000B53</idno><idno type="wicri:Area/Main/Exploration">000B53</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">The effects of sampling on the efficiency and accuracy of <italic>k</italic>−mer indexes: Theoretical and empirical comparisons using the human genome</title><author><name sortKey="Almutairy, Meznah" sort="Almutairy, Meznah" uniqKey="Almutairy M" first="Meznah" last="Almutairy">Meznah Almutairy</name><affiliation><nlm:aff id="aff001"></nlm:aff></affiliation></author><author><name sortKey="Torng, Eric" sort="Torng, Eric" uniqKey="Torng E" first="Eric" last="Torng">Eric Torng</name><affiliation><nlm:aff id="aff001"></nlm:aff></affiliation></author></analytic><series><title level="j">PLoS ONE</title><idno type="eISSN">1932-6203</idno><imprint><date when="2017">2017</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Computational Biology (methods)</term><term>Databases, Genetic</term><term>Genome, Human (genetics)</term><term>Humans</term><term>Sequence Alignment (methods)</term><term>Sequence Analysis, DNA (methods)</term><term>Software</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term><term>Alignement de séquences ()</term><term>Analyse de séquence d'ADN ()</term><term>Bases de données génétiques</term><term>Biologie informatique ()</term><term>Génome humain (génétique)</term><term>Humains</term><term>Logiciel</term></keywords><keywords scheme="MESH" qualifier="genetics" xml:lang="en"><term>Genome, Human</term></keywords><keywords scheme="MESH" qualifier="génétique" xml:lang="fr"><term>Génome humain</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term><term>Sequence Alignment</term><term>Sequence Analysis, DNA</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Databases, Genetic</term><term>Humans</term><term>Software</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Alignement de séquences</term><term>Analyse de séquence d'ADN</term><term>Bases de données génétiques</term><term>Biologie informatique</term><term>Humains</term><term>Logiciel</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><p>One of the most common ways to search a sequence database for sequences that are similar to a query sequence is to use a <italic>k</italic>-mer index such as BLAST. A big problem with <italic>k</italic>-mer indexes is the space required to store the lists of all occurrences of all <italic>k</italic>-mers in the database. One method for reducing the space needed, and also query time, is sampling where only some <italic>k</italic>-mer occurrences are stored. Most previous work uses <italic>hard sampling</italic>, in which enough <italic>k</italic>-mer occurrences are retained so that all similar sequences are guaranteed to be found. In contrast, we study <italic>soft sampling</italic>, which further reduces the number of stored <italic>k</italic>-mer occurrences at a cost of decreasing query accuracy. We focus on finding highly similar local alignments (HSLA) over nucleotide sequences, an operation that is fundamental to biological applications such as cDNA sequence mapping. For our comparison, we use the NCBI BLAST tool with the human genome and human ESTs. When identifying HSLAs, we find that soft sampling significantly reduces both index size and query time with relatively small losses in query accuracy. For the human genome and HSLAs of length at least 100 bp, soft sampling reduces index size 4-10 times more than hard sampling and processes queries 2.3-6.8 times faster, while still achieving retention rates of at least 96.6%. When we apply soft sampling to the problem of mapping ESTs against the genome, we map more than 98% of ESTs perfectly while reducing the index size by a factor of 4 and query time by 23.3%. These results demonstrate that soft sampling is a simple but effective strategy for performing efficient searches for HSLAs. We also provide a new model for sampling with BLAST that predicts empirical retention rates with reasonable accuracy by modeling two key problem factors.</p></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Pearson, Wr" uniqKey="Pearson W">WR Pearson</name></author><author><name sortKey="Lipman, Dj" uniqKey="Lipman D">DJ Lipman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Altschul, Sf" uniqKey="Altschul S">SF Altschul</name></author><author><name sortKey="Madden, Tl" uniqKey="Madden T">TL Madden</name></author><author><name sortKey="Sch Ffer, Aa" uniqKey="Sch Ffer A">AA Schäffer</name></author><author><name sortKey="Zhang, J" uniqKey="Zhang J">J Zhang</name></author><author><name sortKey="Zhang, Z" uniqKey="Zhang Z">Z Zhang</name></author><author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Zhang, Z" uniqKey="Zhang Z">Z Zhang</name></author><author><name sortKey="Schwartz, S" uniqKey="Schwartz S">S Schwartz</name></author><author><name sortKey="Wagner, L" uniqKey="Wagner L">L Wagner</name></author><author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Morgulis, A" uniqKey="Morgulis A">A Morgulis</name></author><author><name sortKey="Coulouris, G" uniqKey="Coulouris G">G Coulouris</name></author><author><name sortKey="Raytselis, Y" uniqKey="Raytselis Y">Y Raytselis</name></author><author><name sortKey="Madden, Tl" uniqKey="Madden T">TL Madden</name></author><author><name sortKey="Agarwala, R" uniqKey="Agarwala R">R Agarwala</name></author><author><name sortKey="Sch Ffer, Aa" uniqKey="Sch Ffer A">AA Schäffer</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Irizarry, K" uniqKey="Irizarry K">K Irizarry</name></author><author><name sortKey="Kustanovich, V" uniqKey="Kustanovich V">V Kustanovich</name></author><author><name sortKey="Li, C" uniqKey="Li C">C Li</name></author><author><name sortKey="Brown, N" uniqKey="Brown N">N Brown</name></author><author><name sortKey="Nelson, S" uniqKey="Nelson S">S Nelson</name></author><author><name sortKey="Wong, W" uniqKey="Wong W">W Wong</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Sachidanandam, R" uniqKey="Sachidanandam R">R Sachidanandam</name></author><author><name sortKey="Weissman, D" uniqKey="Weissman D">D Weissman</name></author><author><name sortKey="Schmidt, Sc" uniqKey="Schmidt S">SC Schmidt</name></author><author><name sortKey="Kakol, Jm" uniqKey="Kakol J">JM Kakol</name></author><author><name sortKey="Stein, Ld" uniqKey="Stein L">LD Stein</name></author><author><name sortKey="Marth, G" uniqKey="Marth G">G Marth</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ng, Pc" uniqKey="Ng P">PC Ng</name></author><author><name sortKey="Henikoff, S" uniqKey="Henikoff S">S Henikoff</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Kent, Wj" uniqKey="Kent W">WJ Kent</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ning, Z" uniqKey="Ning Z">Z Ning</name></author><author><name sortKey="Cox, Aj" uniqKey="Cox A">AJ Cox</name></author><author><name sortKey="Mullikin, Jc" uniqKey="Mullikin J">JC Mullikin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wu, Td" uniqKey="Wu T">TD Wu</name></author><author><name sortKey="Watanabe, Ck" uniqKey="Watanabe C">CK Watanabe</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wandelt, S" uniqKey="Wandelt S">S Wandelt</name></author><author><name sortKey="Leser, U" uniqKey="Leser U">U Leser</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wandelt, S" uniqKey="Wandelt S">S Wandelt</name></author><author><name sortKey="Starlinger, J" uniqKey="Starlinger J">J Starlinger</name></author><author><name sortKey="Bux, M" uniqKey="Bux M">M Bux</name></author><author><name sortKey="Leser, U" uniqKey="Leser U">U Leser</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Danek, A" uniqKey="Danek A">A Danek</name></author><author><name sortKey="Deorowicz, S" uniqKey="Deorowicz S">S Deorowicz</name></author><author><name sortKey="Grabowski, S" uniqKey="Grabowski S">S Grabowski</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Hatem, A" uniqKey="Hatem A">A Hatem</name></author><author><name sortKey="Bozda, D" uniqKey="Bozda D">D Bozdağ</name></author><author><name sortKey="Toland, Ae" uniqKey="Toland A">AE Toland</name></author><author><name sortKey="Catalyurek, Uv" uniqKey="Catalyurek U">ÜV Çatalyürek</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Hach, F" uniqKey="Hach F">F Hach</name></author><author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name></author><author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name></author><author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name></author><author><name sortKey="Birol, I" uniqKey="Birol I">I Birol</name></author><author><name sortKey="Eichler, Ee" uniqKey="Eichler E">EE Eichler</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name></author><author><name sortKey="Kidd, Jm" uniqKey="Kidd J">JM Kidd</name></author><author><name sortKey="Marques Bonet, T" uniqKey="Marques Bonet T">T Marques-Bonet</name></author><author><name sortKey="Aksay, G" uniqKey="Aksay G">G Aksay</name></author><author><name sortKey="Antonacci, F" uniqKey="Antonacci F">F Antonacci</name></author><author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Rumble, Sm" uniqKey="Rumble S">SM Rumble</name></author><author><name sortKey="Lacroute, P" uniqKey="Lacroute P">P Lacroute</name></author><author><name sortKey="Dalca, Av" uniqKey="Dalca A">AV Dalca</name></author><author><name sortKey="Fiume, M" uniqKey="Fiume M">M Fiume</name></author><author><name sortKey="Sidow, A" uniqKey="Sidow A">A Sidow</name></author><author><name sortKey="Brudno, M" uniqKey="Brudno M">M Brudno</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ahmadi, A" uniqKey="Ahmadi A">A Ahmadi</name></author><author><name sortKey="Behm, A" uniqKey="Behm A">A Behm</name></author><author><name sortKey="Honnalli, N" uniqKey="Honnalli N">N Honnalli</name></author><author><name sortKey="Li, C" uniqKey="Li C">C Li</name></author><author><name sortKey="Weng, L" uniqKey="Weng L">L Weng</name></author><author><name sortKey="Xie, X" uniqKey="Xie X">X Xie</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name></author><author><name sortKey="Hach, F" uniqKey="Hach F">F Hach</name></author><author><name sortKey="Sahinalp, Sc" uniqKey="Sahinalp S">SC Sahinalp</name></author><author><name sortKey="Eichler, Ee" uniqKey="Eichler E">EE Eichler</name></author><author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Weese, D" uniqKey="Weese D">D Weese</name></author><author><name sortKey="Emde, Ak" uniqKey="Emde A">AK Emde</name></author><author><name sortKey="Rausch, T" uniqKey="Rausch T">T Rausch</name></author><author><name sortKey="Doring, A" uniqKey="Doring A">A Döring</name></author><author><name sortKey="Reinert, K" uniqKey="Reinert K">K Reinert</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Roberts, M" uniqKey="Roberts M">M Roberts</name></author><author><name sortKey="Hayes, W" uniqKey="Hayes W">W Hayes</name></author><author><name sortKey="Hunt, Br" uniqKey="Hunt B">BR Hunt</name></author><author><name sortKey="Mount, Sm" uniqKey="Mount S">SM Mount</name></author><author><name sortKey="Yorke, Ja" uniqKey="Yorke J">JA Yorke</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Roberts, M" uniqKey="Roberts M">M Roberts</name></author><author><name sortKey="Hunt, Br" uniqKey="Hunt B">BR Hunt</name></author><author><name sortKey="Yorke, Ja" uniqKey="Yorke J">JA Yorke</name></author><author><name sortKey="Bolanos, Ra" uniqKey="Bolanos R">RA Bolanos</name></author><author><name sortKey="Delcher, Al" uniqKey="Delcher A">AL Delcher</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ye, C" uniqKey="Ye C">C Ye</name></author><author><name sortKey="Ma, Zs" uniqKey="Ma Z">ZS Ma</name></author><author><name sortKey="Cannon, Ch" uniqKey="Cannon C">CH Cannon</name></author><author><name sortKey="Pop, M" uniqKey="Pop M">M Pop</name></author><author><name sortKey="Douglas, Wy" uniqKey="Douglas W">WY Douglas</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Chikhi, R" uniqKey="Chikhi R">R Chikhi</name></author><author><name sortKey="Limasset, A" uniqKey="Limasset A">A Limasset</name></author><author><name sortKey="Jackman, S" uniqKey="Jackman S">S Jackman</name></author><author><name sortKey="Simpson, Jt" uniqKey="Simpson J">JT Simpson</name></author><author><name sortKey="Medvedev, P" uniqKey="Medvedev P">P Medvedev</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Abouelhoda, Mi" uniqKey="Abouelhoda M">MI Abouelhoda</name></author><author><name sortKey="Kurtz, S" uniqKey="Kurtz S">S Kurtz</name></author><author><name sortKey="Ohlebusch, E" uniqKey="Ohlebusch E">E Ohlebusch</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Vyverman, M" uniqKey="Vyverman M">M Vyverman</name></author><author><name sortKey="De Baets, B" uniqKey="De Baets B">B De Baets</name></author><author><name sortKey="Fack, V" uniqKey="Fack V">V Fack</name></author><author><name sortKey="Dawyndt, P" uniqKey="Dawyndt P">P Dawyndt</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Khiste, N" uniqKey="Khiste N">N Khiste</name></author><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Xin, H" uniqKey="Xin H">H Xin</name></author><author><name sortKey="Lee, D" uniqKey="Lee D">D Lee</name></author><author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name></author><author><name sortKey="Yedkar, S" uniqKey="Yedkar S">S Yedkar</name></author><author><name sortKey="Mutlu, O" uniqKey="Mutlu O">O Mutlu</name></author><author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name></author></analytic></biblStruct></listBibl></div1></back></TEI><affiliations><list></list><tree><noCountry><name sortKey="Almutairy, Meznah" sort="Almutairy, Meznah" uniqKey="Almutairy M" first="Meznah" last="Almutairy">Meznah Almutairy</name><name sortKey="Torng, Eric" sort="Torng, Eric" uniqKey="Torng E" first="Eric" last="Torng">Eric Torng</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000B53 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000B53 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= PMC:5501444
|texte= The effects of sampling on the efficiency and accuracy of k−mer indexes: Theoretical and empirical comparisons using the human genome
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:28686614" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |